package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.rmi.dgc.DGC;
import java.util.*;

public class No1415长度为n的开心字符串中字典序第k小的字符串 {

    /**
     * 一个 「开心字符串」定义为：
     *
     * 仅包含小写字母 ['a', 'b', 'c'].
     * 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。
     * 比方说，字符串 "abc"，"ac"，"b" 和 "abcbabcbcb" 都是开心字符串，但是 "aa"，"baa" 和 "ababbc" 都不是开心字符串。
     *
     * 给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。
     *
     * 请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：n = 1, k = 3
     * 输出："c"
     * 解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。
     * 示例 2：
     *
     * 输入：n = 1, k = 4
     * 输出：""
     * 解释：长度为 1 的开心字符串只有 3 个。
     */

    char[] arr={'a','b','c'};
    String res="";
    int count;

    //用a,b,c这三个字符组合长度为n的开心数,输出排在第k位的开心数
    public String getHappyString(int n, int k) {
        StringBuilder stringBuilder = new StringBuilder();
        dg(n,k,stringBuilder);
        return res;
    }

    private void dg(int n,int k,StringBuilder path){

        if(n==path.length()) {
            count++;
            return;//path后面不需要再新增字符了
        }

        for(int i=0;i<3;i++){
            if(path.length()>0&&arr[i]==path.charAt(path.length()-1))
                continue;//跳过本次遍历
            path.append(arr[i]);
            dg(n,k,path);
            if(k==count){
                res=path.toString();
                return;//停止遍历
            }
            path.deleteCharAt(path.length()-1);
        }

    }



    public static void main(String[] args) {
        No1415长度为n的开心字符串中字典序第k小的字符串 n=new No1415长度为n的开心字符串中字典序第k小的字符串();
        String happyString = n.getHappyString(12, 12);
        System.out.println(happyString);
    }

}
